package stack_queue.queue.impl;

import stack_queue.queue.Queue;

import java.util.NoSuchElementException;

// 基于链表的队列
// 队首出，队尾进
public class LinkedQueue implements Queue {
    private Node head;
    private Node tail;
    private int size;
    private class Node {
        private int data;
        private Node next;
        public Node(int data) {
            this.data = data;
        }
    }

    /**
     * 入队操作
     * @param value
     */
    @Override
    public void offer(int value) {
        // 新元素
        Node node = new Node(value);
        if (head == null) {
            head = tail = node;
        }else {
            tail.next = node;
            tail = node;
        }
        size ++;
    }

    @Override
    public int poll() {
        if (size == 0) {
            throw new NoSuchElementException("队列为空!");
        }
        int oldValue = head.data;
        Node tmpHead = head;
        head = head.next;
        tmpHead.next = null;
        size --;
        return oldValue;
    }

    @Override
    public int peek() {
        if (size == 0) {
            throw new NoSuchElementException("队列为空!");
        }
        return head.data;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("front [");
        Node node = head;
        while (node != null) {
            sb.append(node.data);
            if (node.next != null) {
                sb.append(",");
            }
            node = node.next;
        }
        sb.append("] tail");
        return sb.toString();
    }
}
